package st

var lg2 = []int32{0, 0}

type NormalList interface {
	Len() int32
	ILoc(a int32) interface{}
}

type cmp func(interface{}, interface{}) interface{}
type cmpInt func(int, int) int
type cmpInt32 func(int32, int32) int32

var f cmp
var fInt cmpInt
var fInt32 cmpInt32

func lg2Gen(n int32) {
	// n + 1
	if int32(len(lg2)) <= n {
		for i := int32(len(lg2)); i <= n; i++ {
			lg2 = append(lg2, lg2[i>>1]+1)
		}
	}
}

func ST(v NormalList, fun cmp) [][]interface{} {
	n := v.Len()
	f = fun

	lg2Gen(n)

	var sts [][]interface{}
	sts = append(sts, make([]interface{}, n))
	for i := int32(0); i < n; i++ {
		sts[0][i] = v.ILoc(i)
	}
	for i := int32(1); (int32(1) << i) <= n; i++ {
		sts = append(sts, make([]interface{}, n))
		for j := int32(0); j <= n-(1<<i); j++ {
			sts[i][j] = f(sts[i-1][j], sts[i-1][j+(1<<(i-1))])
		}
	}
	return sts
}

func Query(sts [][]interface{}, l, r int) interface{} {
	lg := lg2[r-l+1]
	return f(sts[lg][l], sts[lg][r-(1<<lg)+1])
}

func STInt(v []int, fun cmpInt) [][]int {
	n := int32(len(v))
	fInt = fun

	lg2Gen(n)

	var sts [][]int
	sts = append(sts, make([]int, n))
	for i := int32(0); i < n; i++ {
		sts[0][i] = v[i]
	}
	for i := int32(1); (int32(1) << i) <= n; i++ {
		sts = append(sts, make([]int, n))
		for j := int32(0); j <= n-(1<<i); j++ {
			sts[i][j] = fInt(sts[i-1][j], sts[i-1][j+(1<<(i-1))])
		}
	}
	return sts
}

func QueryInt(sts [][]int, l, r int) int {
	lg := lg2[r-l+1]
	return fInt(sts[lg][l], sts[lg][r-(1<<lg)+1])
}

func STInt32(v []int32, fun cmpInt32) [][]int32 {
	n := int32(len(v))
	fInt32 = fun

	lg2Gen(n)

	var sts [][]int32
	sts = append(sts, make([]int32, n))
	for i := int32(0); i < n; i++ {
		sts[0][i] = v[i]
	}
	for i := int32(1); (int32(1) << i) <= n; i++ {
		sts = append(sts, make([]int32, n))
		for j := int32(0); j <= n-(1<<i); j++ {
			sts[i][j] = fInt32(sts[i-1][j], sts[i-1][j+(1<<(i-1))])
		}
	}
	return sts
}

func QueryInt32(sts [][]int32, l, r int) int32 {
	lg := lg2[r-l+1]
	return fInt32(sts[lg][l], sts[lg][r-(1<<lg)+1])
}
